/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 迭代：双色标记法
// 后序遍历：LRN, 入栈：NRL
type Color struct {
	Color int
	Node  *TreeNode
}

func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	var res []int

	s := []*Color{&Color{0, root}}
	for len(s) > 0 {
		c := s[len(s)-1]
		s = s[:len(s)-1]

		if c.Color == 1 {
			res = append(res, c.Node.Val)
		} else {
			s = append(s, &Color{1, c.Node})
			if c.Node.Right != nil {
				s = append(s, &Color{0, c.Node.Right})
			}
			if c.Node.Left != nil {
				s = append(s, &Color{0, c.Node.Left})
			}
		}
	}

	return res
}